package questoes.q6;


public class Main {

	private static int encontrarMaiorLinha(int[][] matriz, int linhaOrigem1, 
   int linhaDestino1, int linhaOrigem2, int linhaDestino2){

		System.out.println(linhaOrigem1 + " " + linhaDestino1 + " " + linhaOrigem2 + " " + linhaDestino2);
		
		if(linhaOrigem1 == linhaDestino1 && linhaOrigem2 == linhaDestino2){
			for(int i = 0; i < matriz[linhaOrigem1].length; i++){

				if(matriz[linhaOrigem1][i] == 0){
					return linhaOrigem2;
				}

				else if(matriz[linhaOrigem2][i] == 0){
					return linhaOrigem1;
				}

			}

			return -1;

		}

		else{

			int maior1 = -1;

			if(linhaOrigem1 != linhaDestino1){
				maior1 = encontrarMaiorLinha(matriz, linhaOrigem1, linhaDestino1 / 2, (linhaDestino1 / 2) + 1, linhaDestino1);
			}

			int maior2 = -1;

			if(linhaOrigem2 != linhaDestino2){
				maior2 = encontrarMaiorLinha(matriz, linhaOrigem2, (linhaDestino2 + linhaDestino1) / 2, 
            ((linhaDestino2 + linhaDestino1) / 2) + 1, linhaDestino2);
			}

			return encontrarMaiorLinha(matriz, maior1, maior1, maior2, maior2);

		}

	}

	public static void main(String[] args) {

		int[][] matriz = new int[][]{
				{1, 1, 1, 1, 1, 1},
				{1, 1, 1, 1, 1, 0},
				{0, 0, 0, 0, 0, 0},
				{1, 1, 0, 0, 0, 0},
				{1, 1, 1, 1, 0, 0},
				{1, 1, 1, 0, 0, 0}
		};
		
		System.out.println(encontrarMaiorLinha(matriz, 0, matriz.length / 2, 
      (matriz.length / 2) + 1, matriz.length - 1));

	}

}
